/*
	top = 0表示栈空的初始状态，top指向栈顶在数组的位置
	top = stacksize - 1 表示栈满
	进栈首先top加1，初始为0，先加1在进栈会造成数组第一个空间没被利用
	出栈先执行在减1
*/

#define MAX_STACK_SIZE 100 /*大小*/
typedef int ElemType;
typedef int Status;
typedef int ERROR;
typedef int OK;

typedef struct sqstack
{
	ElemType Elem_array[MAX_STACK_SIZE];
	int top;
}SqStack;

//初始化一个栈
SqStack Init_Stack(void)
{
	SqStack S;
	S.top = 0;
	return(S);
}

//压栈
Status push(SqStack S,ElemType e)
{//元素e成为新的栈顶
	if (S.top = MAX_STACK_SIZE - 1)
		return ERROR;
	S.top++;
	S.Elem_array[S.top] = e;
	return OK;
}

//弹栈
Status pop(SqStack S,ElemType *e)
{
	if (S.top == 0)
		return ERROR;
	*e = S.Elem_array[S.top];
	S.top--;
	return OK;
}

/*
	利用栈进行数制转换：十进制向其他进栈进行转换
	n      n div 8    n mod m
	1348   168        4
	168    21         0
	21     2          5
	2      0          2
	1348的八进制为2504
*/
void conversion(int n ,int d)
{
	SqStack S;
	int i,k;
	S = Init_Stack();
	while (n > 0)
	{
		n = n/d;
		k = n%d;
		push(S,k);
	}

	while (S.top != 0)
	{
		pop(S,i);
		printf("%ld\n",e);
	}

}



/*
	括号匹配问题:从左至右扫描一个字符串(或表达式)，
	每个右括号将与最近遇到的那个左括号相匹配。
	可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈中。
	每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相
	匹配，同时从栈顶删除该元素

	设置一个栈，当读到左括号时左括号进栈。当读到右括号时，则从
	栈中弹出一个元素，与独到的左括号进行匹配，若匹配成功，继续
	读入;失败返回false
*/
int match(const char a[])
{
	SqStack S;
	S = Init_Stack();
	int i = strlen(a);
	int k = 0;
	while (k < i)
	{
		if (a[k] == '[' || a[k] == '(')
		{
			push(S,a[k++]);
		}
		else if (a[k] == ']')
		{
			int *x;
			pop(S,x);
			if (*x != '[')
			{
				printf("括号不匹配\n");
				return FALSE;
			}
		}
		else if (a[k] == ')')
		{
			int *x;
			pop(S,x);
			if (*x != '(')
			{
				printf("括号不匹配\n");
				return FALSE;
			}
		}
	}

	return OK;
}


/*
	表达式求值
	中缀表达式 A+B
	前缀表达式 +AB
	后缀表达式 AB+

	中缀表达式 a + b * (c - d) - e / f
	后缀表达式 a b c d - * + e f / -

	a:优先级高的先计算
	b:优先级相同的自左向右计算
	c:当使用括号时，从最内层括号开始计算

	当使用中缀表达式计算时,需要同时使用两个栈进行辅助求值
	使用后缀表达式求值，则只需一个栈，相对简单一些
*/
/*
	中缀表达式转化为后缀表达式算法
	··作符栈初始化，将结束符"#"进栈。然后读入中缀表达式字符流
	  首字符
	··重复执行以下步骤,直到为"#",同时栈顶也是"#"，停止循环
	··a.若是操作数，直接输出，读入下一个字符
	··b.若是操作符，判断优先级和位于栈顶的操作符的优先级：
		··若操作符的优先级比栈顶操作符高，进栈，读下一个
		··若低于，退栈输出
		··相等退栈不输出，若退出的是")"，读入下一个
*/